A plurality of clients can share a single access link to the Internet or other IP network by using network address and port translation. In accordance with NAT, the clients on a private network are assigned individual IP addresses from a pool of IP addresses reserved by the Internet Assigned Numbers Authority (IANA) for non-exclusive private network use. Private addresses are not routable on the Internet. When a client on the private network wants to communicate with a server on a global network, such as the Internet, a globally unique and routable IP address must be used instead of the client's local non-routable private IP address. Typically, a private network is connected to the Internet via a router and shared access link to an Internet Service Provider (ISP). NAT is a feature that may be implemented in the router and that provides unambiguous translations between private and global addresses, allowing the plural clients to share the access link. When a client sends a packet to a foreign address (i.e., one not in the private network), NAT modifies the packet header, substituting the client's private source IP address and generalized port number (GPN) by a global IP address and GPN. Depending upon the protocol being used, GPN is a certain field in the packet header. For example, for the TCP or UDP protocols, the GPN is the TCP or UDP port number. For other protocols, the GPN may be another field. A single global IP address may be shared as the source address of packets sent by all or some of the clients to the Internet. In order to properly route incoming packets sent from a foreign address on the Internet to a client on the private network, NAT maintains, in a translation table in memory, the one-to-one correspondence between private and global IP addresses and GPNs. When NAT receives a packet from the Internet, NAT modifies the packet header's destination from global to private (IP address, GPN) values, according the NAT's translation table, allowing the packet to reach the respective client in the private network. Some application-layer protocols may also include IP addresses and possibly port numbers in packet payloads. Such addresses and port numbers must also be similarly translated. For each such protocol, NAT includes an Application Level Gateway (ALG) program that provides these additional necessary translations. Furthermore, when the NAT performs its translations, the packet checksum in the transport layer TCP or UDP header of the packet is correspondingly modified to reflect the changes resulting from the translations. Thus, when the packet is eventually received at its destination, its checksum will be correct if there are no transmission errors.
The use of network address translation presents difficulties when it does not or cannot support a particular protocol that a client is desirous of using. As an example, certain security architectures have not been able to be fully interoperable with NAT. Security protocols are extremely useful in determining whether or not a received packet has been corrupted in some manner between the client/servers from which it is transmitted and received. In order to prevent packet forgery and snooping, authentication and encryption of packets may be used, respectively. Various security protocols may be used for authentication and/or encryption. Some protocols can be used in conjunction with NAT, for example the Secure Shell (SSH), Secure Sockets Layers (SSL), and Point-to-Point Tunneling Protocol (PPTP). Disadvantageously, however, SSH and SSL implement security in the application layer and are thus application-dependent, whereas PPTP's security is often considered deficient. On the other hand, the IP Security (IPSec) protocol operates at the network layer and therefore is independent of the transport- (e.g., TCP or UDP) or application-layer protocol (e.g., HTTP, FTP, or TELNET). It is thus application independent and therefore capable of providing end-to-end security without modification to applications. Further, IPSec is vendor-independent and can provide end-to-end security. Disadvantageously, however, IPSec has been considered as not being interoperable with NAT. In fact, the literature has so stated (see, e.g., M. Doraswamy and D. Harkins, “IPSEC: The New Security Standard for the Internet, Intranets and Virtual Private Networks,” Prentice-Hall, 1st ed., July 1999).
IPSec is an Internet standard from the IETF IPSec Working Group (see, e.g., S. Kent and R. Atkinson, “Security Architecture for the Internet Protocol,” IETF, RFC 2401, November 1998). IPSec is a mandatory part of the next-generation IP protocol (IPv6, see, e.g., S. Deering and R. Hinden, “Internet Protocol, Version 6 (Ipv6) Specification,” IETF, RFC 2460, December 1998), but most existing IPSec implementations assume current-generation IP (IPv4). IPSec is essentially an encapsulation protocol, namely one that defines the syntax and semantics of placing one packet inside another. IPSec defines two protocols, the Authentication Header (AH) protocol (see, e.g., S. Kent and R. Atkinson, “IP Authentication Header,” IEFT, RFC 2402, November 1998) and Encapsulating Security Payload (ESP) protocol (see, e.g., S. Kent and R. Atkinson, “IP Encapsulating Security Payload (ESP),” IEFT, RFC 2406, November 1998). The AH protocol can provide authentication of packet origin, proof of integrity of packet data, and protection against packet replay. In addition to that which the AH protocol can provide, the ESP protocol can provide encryption of packet data and limited traffic flow confidentiality. The AH and ESP protocols can be used either in what are known as the transport or tunnel modes. The transport mode provides end-to-end security between the source of the packet and its destination. In contrast, the tunnel mode encapsulates packets and thus provides security between the nodes where the packet is encapsulated and decapsulated, which can be any nodes (e.g., routers) on the path between the source of the packet and its destination. Depending on the situation, clients might use different modes. Thus, for example, the transport mode may be used to download, via FTP, a document from a supplier's server, thus providing full authentication/security between the client and the server. On the other hand, a client can use the tunnel mode to connect to an IPSec gateway onto an employer's Intranet.
Several problems hamper the interoperation of IPSec and NAT. For the AH protocol, when NAT translates an address, it would need to correspondingly adjust, through an ALG program, the packet's authentication data, which depends on the packet's address. If the authentication data is not adjusted the packet will be rejected at the destination. In order for the NAT to modify the authentication data, however, the NAT would need to know the authentication key. Since that key is maintained private in order to protect the integrity of the security architecture, NAT is unable to modify the authentication data in the packet to compensate for the address translations. Thus, NAT, as it is conventionally used, is not interoperable with the AH protocol. For the ESP protocol, interoperability with NAT is problematic in the transport mode. In the transport mode of the ESP protocol, when NAT translates the source or destination IP address, it would need to correspondingly adjust the TCP or UDP checksum, which is calculated over the packet's IP “pseudo-header,” TCP or UDP header, and packet data. The pseudo-header includes the source and destination IP addresses. However, since the checksum is encrypted, along with the rest of the TCP or UDP header and data, NAT cannot make the necessary adjustment to this checksum without having access to the encryption key. For end-to-end security, the encryption key must not be revealed to intermediate nodes including NAT. Thus, NAT is also not interoperable with the ESP protocol in the transport mode. In co-pending patent applications entitled “Method and Apparatus for Application-Independent End-to-End Security in Shared-Link Access Networks, Ser. No. 09/698,978, and “Method and Apparatus for Extending Network Address Translations for Unsupported Protocol”, Ser. No. 09/698,973, both filed Oct. 27, 2000, both incorporated herein by reference, a technique is described for extending NAT to be capable of providing network address translation of outgoing and incoming packets from and directed to clients, respectively, operating under a protocol that NAT itself does support such as, for example, IPSec. As described in these co-pending applications, NAT is extended by creating entries in a translation table when it receives a request from a client using a protocol that it does not support, such as IPSec's AH protocol or the ESP protocol in the transport mode. Further, ALGs that would otherwise be needed at the NAT are included at the client, which also pre-compensates outgoing packets before they are transmitted and post-compensates incoming packets for the effects on the packets of the NAT's translation. These techniques advantageously enable NAT interoperability with unsupported protocols, such as IPSec, but require modification of the NAT itself.
With respect to other IPSec protocols such as IKE (see, e.g., D. Maughan, M. Schertler, M. Schneider and J. Turner, “Internet Security Association and Key Management Protocol [ISAKMP],” IETF, RFC 2408, November 1998; and D. Harkins and D. Carrel, “The Internet Key Exchange (IKE),” IETF, RFC 2409, November 1998) and the ESP tunnel protocol, Linux's NAT implementation, called IP Masquerade, includes a feature called VPN Masquerade, which provides NAT interoperation with the IKE and ESP tunnel protocols. IKE is used for negotiation of cryptographic protocols, algorithms, and keys and the ESP tunnel mode is described above. NAT support for these protocols is possible because they do not authenticate or encrypt any information that depends on the IP header of the packet itself (IKE) or encapsulating packet (ESP tunnel mode), unlike the AH and ESP transport modes.
VPN Masquerade running on NAT translates only the source or destination IP address of IKE packets and ESP tunnel mode encapsulating packets. In this regard, VPN Masquerade differs markedly from IP Masquerade's handling of TCP and UDP packets. In the latter cases, IP Masquerade also translates the source or destination port number, so that all clients can use the same global IP address, and NAT can identify the particular client using the port number. Similar translations in IKE and ESP tunnel mode are not possible because port numbers and other identifiers are cryptographically protected.
In the following, “client” denotes a computer connected to a private network that is in turn connected to the Internet through a NAT, and “server” denotes a computer connected to the Internet and not connected to the aforementioned private network.
Because all clients share a single global IP address, VPN Masquerade allows, by default, at most one IKE and one ESP session between clients and any given server. When a packet returns from the server, VPN Masquerade uses the server's IP address to identify the corresponding client. If a client sends an IKE or ESP packet to a server that has an ongoing IKE or ESP session with another client, respectively, VPN Masquerade drops that packet.
The limitation of at most one client per server may be acceptable for certain situations, such as in a home office. It is not, however, acceptable for other situations, such as in a conference center, where multiple attendees may work for the same company and simultaneously want to access the respective VPN server back in their home office. In the latter cases, VPN Masquerade may be configured to operate without this limitation, using the techniques and heuristics described below.
When more than one client may access the same server, VPN Masquerade identifies the particular client by checking the server's IP address and, for IKE, the initiator and responder cookies, or, for ESP, the incoming SPI (Security Parameters Index). Cookies and SPIs are transmitted unencrypted in IKE and ESP headers, respectively. Each cookie has 64 bits and is selected randomly at the beginning of an IKE session to uniquely identify the session within the respective IPSec peer (see, Maughan et al., “Internet Security Association and Key Management Protocol,” cited above). SPIs have 32 bits and are randomly selected during an IKE negotiation to uniquely identify a security association (SA) in the respective destination IPSec peer (see, Kent et al. “Security Architecture for the Internet Protocol,” cited above). Each epoch of an ESP tunnel is defined as the combination of two SAs, one in each direction. SAs always have a limited lifetime, after which an IKE negotiation takes place to establish a new epoch's SAs with new keys and SPIs. SPIs are transmitted encrypted in IKE negotiations. The negotiations to establish each new epoch's SAs with new keys and SPIs begin at a certain time before the end of an epoch, and may be started by either the client or server. Once negotiations are completed, a switchover to the new epoch immediately takes place. Such overlap between epochs is necessary to enable renegotiation of keys and SPIs for the new epoch before the previous epoch has ended.
VPN Masquerade handles IKE as follows. VPN Masquerade maintains a hash table of items containing client and server IP addresses and initiator and responder cookies. Each item corresponds to an IKE session. An item is considered outstanding or established according to whether the responder cookie is null or not, respectively. When a client sends a packet such that no item in the table matches the client and server IP addresses and initiator cookie, VPN Masquerade creates an outstanding item containing those values. Conversely, when a server sends a packet such that no established item in the table matches the server IP address and initiator and responder cookies, but an outstanding item matches the server IP address and initiator cookie, VPN Masquerade converts that item into an established one, including the packet's responder cookie. VPN Masquerade then forwards the packet to the corresponding client.
VPN Masquerade allows more than one client to use the same initiator cookie with the same server. This is possible because each client chooses initiator cookies independently. It is thus possible, but highly unlikely, that two clients would choose the same initiator cookie. Specifically, if n clients simultaneously have an IKE session with the same server and use “good” random number generators, the probability of such a collision of initiator cookies is about (n−1)/(264). VPN Masquerade correctly handles the unlikely situation when more than one client has the same initiator cookie by using the responder cookie to correctly identify the client. To do this, VPN Masquerade needs to slightly modify the above rules and serialize the initial IKE handshake as follows. When a client C1 sends a packet whose client and server IP addresses and initiator cookie match no item in the table, but whose server IP address and initiator cookie match another client C2's outstanding item, VPN Masquerade drops that packet. Eventually, when C1's IKE implementation retries the transmission, after timeouts, C2's item will already be established, and VPN Masquerade will forward C1's packet normally.
VPN Masquerade handles ESP as follows. VPN Masquerade maintains a hash table of items containing client and server IP addresses and outgoing and incoming SPIs. Each item corresponds to an ESP tunnel's epoch, between successive rekeyings. An item is considered outstanding or established according to whether the incoming SPI is null or not, respectively. When a client sends a packet such that no item in the table matches the client and server IP addresses and outgoing SPI: (1) if the server IP address matches no outstanding item, VPN Masquerade creates an outstanding item containing the client and server IP addresses and outgoing SPI; (2) otherwise, VPN Masquerade drops the packet. Conversely, when a server sends a packet such that no established item matches the server IP address and incoming SPI: (1) if an outstanding item matches the server IP address, VPN Masquerade converts that item into an established one, including the packet's incoming SPI, and forwards the packet to the corresponding client; (2) otherwise, VPN Masquerade multicasts the packet to all clients that have recently had an IKE negotiation with the server. To thwart denial of service attacks, VPN Masquerade: (1) times out outstanding items after a short period, Tout; (2) after an outstanding ESP item of client C1 causes a packet of another client C2 to be dropped, limits to a maximum value, Nout, the number of packets that C1 may send matching the outstanding item; and (3) times out established items after a period of inactivity Tei.
VPN Masquerade, as it currently exists, does not support fail-over recovery and is susceptible to various failure conditions that can cause it to demultiplex incoming packets incorrectly. As an example of the former, a private domain may be multi-homed and connected to the Internet via instances A and B of VPN Masquerade. If a client establishes an ESP tunnel to a server via VPN Masquerade instance A and A crashes, the client's ESP packets may be routed via VPN Masquerade instance B and reach the server, but the server's ESP packets may continue to be sent to the failed A and therefore never reach the client.
As noted, VPN Masquerade's heuristics for demultiplexing ESP packets may also cause it to demultiplex incoming packets incorrectly.
VPN Masquerade's hash tables can be viewed as soft and possibly in an incorrect state. VPN Masquerade loses state, e.g., when an item times out or VPN Masquerade crashes, but automatically reacquires state when subjected to further traffic. However, before or after recovery, VPN Masquerade's state may be incorrect.
In IKE's case, VPN Masquerade's state may at times be incomplete, but it is not incorrect (i.e., it does not incorrectly associate client and server IP addresses and initiator and responder cookies). Additionally, IKE has built-in timeouts and retry mechanisms that will promote recovery of VPN Masquerade's state, if necessary.
Similar recoverability does not exist, however, in ESP's case. VPN Masquerade's state may be incomplete, incorrect (i.e., may incorrectly associate client and server IP addresses and outgoing and incoming SPIs), or both. Additionally, ESP does not have built-in mechanisms that promote timely recovery from losses or errors in VPN Masquerade's state.
The first source of errors in VPN Masquerade's ESP state is incoming SPI collisions. As previously noted, this is possible because each client chooses incoming SPIs independently. This is, however, a rare event since if n clients have an ESP tunnel to the same server and use “good” random number generators, the probability of an incoming SPI collision each time a tunnel is created or rekeyed is approximately (n−1)/(232). When such an event happens, VPN Masquerade will forward to the client whose item is first established all packets sent by the server using the given incoming SPI, and remaining clients will not receive their packets.
The second source of errors in VPN Masquerade's ESP state is race conditions that may cause misassociation of outgoing and incoming SPIs. VPN Masquerade implicitly assumes that, after a tunnel is created or rekeyed, or the corresponding item in the table is timed out, or VPN Masquerade recovers from a crash, that the client uses the tunnel to send a packet to the server before the server sends a packet to the client, and, shortly after receiving this packet (but not before), the server uses the tunnel to send a packet back to the client. These assumptions may be violated in a number of cases described below.
A first race condition is described with reference to FIG. 1 where client C is shown having a tunnel T to server S through VPN Masquerade 101. If there is no outstanding item that matches S and S uses tunnel T before C does (e.g., C was downloading a file when T was rekeyed), VPN Masquerade 101 then has to multicast the packet to all clients that have recently had an IKE negotiation with the server, an inefficient use of resources.
A second race condition is described with reference to FIG. 2, where a race condition can occur when two clients C1 and C2 key or rekey their tunnels T1 and T2, respectively, through a NAT running VPN Masquerade 201, to the same server S at approximately the same time. If C1 sends a packet to S on T1 and S thereafter sends a packet to C2 on T2 before sending a packet to C1, the outstanding item created at VPN Masquerade 201 using C1's outgoing SPI will be associated with C2's incoming SPI. The packet then destined to C2 will be sent instead to C1, which will drop it when it is received. C2 will have its own outstanding item, but when subsequent packets destined for C2 arrive from server S, these packets will be sent to C1 since an established item already exists between C1 and S. Thus, C2 doesn't get its packets sent by S. Also, C1 doesn't get its packets sent by S since it cannot create a new outstanding item in view of the fact that its outgoing SPI is already used in the established item. Thus, neither C1 nor C2 receive their packets sent by S and the NAT running VPN Masquerade 201 must be rebooted to correct the problem.
With reference again to FIG. 2, a third race condition occurs when Cl sends a packet on T1, creating an outstanding item. Before S replies, however, C1's outstanding item expires since an item expires if it is not established within a defined short time after it is created. Restricting the time an item is permitted to remain outstanding is necessary since no other client is allowed to have an outstanding item to S while an item is outstanding. An item that remains outstanding for a long period of time could thus otherwise tie up traffic between another client on the same private network and the server. After Cl's outstanding item expires, C2 then sends a packet to S on T2, creating a new outstanding item for C2, which is now allowed since the other outstanding item for C1 has been removed. S then finally replies to C1, thereby creating an established item with C2's outgoing SPI and C1's incoming SPI. C2 will then receive C1's packets and not its own, and C1 will not receive its packets at all.
Again referring to FIG. 2, a fourth race condition occurs when both C1 and C2 have established tunnels T1 and T2, respectively, to S for a long period of time. Both established items may expire if not used for some period time even though the tunnel remains extant (same keys, same SPIs). After the entries for both C1 and C2 expire, C2 sends a packet to S, creating an outstanding item for C2. S then sends a packet to C1, again creating an established item between C2's incoming SPI and C1's outgoing SPI. As in the previous race conditions, neither C1 nor C2 receive their respective packets.
As described, VPN Masquerade failures may cause it to forward ESP packets to clients other than the intended recipients. ESP preserves security in spite of these errors, because ESP's verification of packet authenticity and/or decryption depends on keys held only by the packets's intended recipient, and other clients simply drop the misdelivered packets. However, VPN Masquerade failures may also prevent the intended recipients from receiving their ESP packets. In this regard, neither ESP nor IKE nor higher-level protocols (e.g., TCP) provide timely recovery. IKE may clear collisions and misassociations when the lifetimes of the tunnels involved expire, but lifetimes are often long, lasting at least several hours.